﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;

namespace MapColoring.MontadorMapa
{
    /// <summary>
    /// Representação do mapa a ser colorido pelo algoritmo CSP
    /// </summary>
    public class Mapa
    {
        #region Campos Privados

        private List<Ponto> pontos;
        private List<Ponto[]> pontosLigados;

        private List<int> pontosSemConexao;

        private double[][] distanciaPontos;

        private Random rng;

        private List<Triangulo> triangulos;
        private List<Triangulo[]> triangAdjacentes;

        private List<int> variaveis;
        private List<int[]> restricoes;

        #endregion

        #region Propriedades

        /// <summary>
        /// Variáveis do CSP
        /// </summary>
        public List<int> Variaveis
        {
            get { return variaveis; }
            set { variaveis = value; }
        }

        /// <summary>
        /// Restrições entre as variáveis do csp
        /// </summary>
        public List<int[]> Restricoes
        {
            get { return restricoes; }
            set { restricoes = value; }
        }

        #endregion

        #region Construtor

        /// <summary>
        /// Representação do mapa a ser colorido pelo algoritmo CSP
        /// </summary>
        public Mapa()
        {
            this.pontos = new List<Ponto>();
            this.pontosLigados = new List<Ponto[]>();
            this.pontosSemConexao = new List<int>();
        }

        #endregion

        /// <summary>
        /// Monta o mapa do problema a ser resolvido com CSP
        /// </summary>
        public void montarMapa(int nPontos, Random rng)
        {
            //Gera n pontos aleatoriamente
            this.rng = rng;
            for (int i = 0; i < nPontos; i++)
            {
                Ponto ponto = new Ponto(this.rng.NextDouble(), this.rng.NextDouble(), i + 1);
                this.pontos.Add(ponto);
            }

            //Calcula distância entre os pontos
            this.distanciaPontos = new double[this.pontos.Count][];
            for (int i = 0; i < pontos.Count; i++)
            {
                this.distanciaPontos[i] = new double[this.pontos.Count];
                for (int j = 0; j < pontos.Count; j++)
                {
                    this.distanciaPontos[i][j] = Geometria.Distancia(this.pontos[i], this.pontos[j]);
                    if (i == j)
                        this.distanciaPontos[i][j] = 4;
                }
            }
            
            this.ligaPontos();
            
            this.acharTriangulos();
            this.acharTriangAdjacentes();
            this.montaVariaveisRestricoes();

            //Para Debug
            //this.imprimeDados(@"C:\Users\Danilo\Documents\arquivo.csv");
        }

        #region Ligação Pontos

        /// <summary>
        /// Liga os pontos utilizando o algoritmo descrito no enunciado do exercício
        /// </summary>
        private void ligaPontos()
        {
            // Não há mais conexões disponíveis
            if (this.pontosSemConexao.Count == this.pontos.Count)
                return;

            //Seleciona aleatoriamente um ponto X
            int indiceX = this.rng.Next(this.pontos.Count);
            while (this.pontosSemConexao.Contains(indiceX))
            {
                indiceX = this.rng.Next(this.pontos.Count);
            }

            int indiceY = this.retornaMenorDistancia(indiceX);
            bool fezConexao = false;

            while (!fezConexao && indiceY != -1)
            {
                // connecta X ao ponto mais próximo Y 
                Ponto x = this.pontos[indiceX];
                Ponto y = this.pontos[indiceY];

                bool retaIntercepta = false;
                
                // desde que X não esteja conectado com Y
                if(this.estaoConectados(x, y))
                {
                    //invalida conexao entre x e y
                    this.distanciaPontos[indiceX][indiceY] = 4;
                    this.distanciaPontos[indiceY][indiceX] = 4;
                }

                // e a nova reta não cruza com nenhuma outra
                for (int i = 0; i < this.pontosLigados.Count; i++)
                {
                    if (Geometria.Intercepta(x, y, this.pontosLigados[i][0], this.pontosLigados[i][1]))
                    {
                        retaIntercepta = true;

                        //invalida conexao entre x e y
                        this.distanciaPontos[indiceX][indiceY] = 4;
                        this.distanciaPontos[indiceY][indiceX] = 4;

                        break;
                    }
                }

                //cria nova conexão
                if (!retaIntercepta)
                {
                    this.pontosLigados.Add(new Ponto[]{x, y});

                    //invalida conexao entre x e y
                    this.distanciaPontos[indiceX][indiceY] = 4;
                    this.distanciaPontos[indiceY][indiceX] = 4;

                    fezConexao = true;
                }

                indiceY = this.retornaMenorDistancia(indiceX);
            }

            if (indiceY == -1)
            {
                this.pontosSemConexao.Add(indiceX);
            }

            ligaPontos();
        }

        /// <summary>
        /// Verifica qual ponto possui a menor distância para o ponto de indice indicePonto
        /// </summary>
        /// <param name="indicePonto"> indice (começa em zero) da lista de Pontos</param>
        /// <returns>indice (começa em zero) da lista de Pontos com a menor distância. 
        /// Se não houver ponto disponível, retorna -1</returns>
        private int retornaMenorDistancia(int indicePonto)
        {
            double menorDistancia = 3;
            int indiceMenorDistancia = -1;

            for (int i = 0; i < this.pontos.Count; i++)
            {
                if (this.distanciaPontos[indicePonto][i] < menorDistancia)
                {
                    indiceMenorDistancia = i;
                    menorDistancia = this.distanciaPontos[indicePonto][i];
                }
            }

            return indiceMenorDistancia;
        }

        /// <summary>
        /// Verifica se os pontos p1 e p2 já estão conectados
        /// </summary>
        /// <param name="p1">Ponto 1</param>
        /// <param name="p2">Ponto 2</param>
        /// <returns>true, se p1 estiver conectado com p2</returns>
        private bool estaoConectados(Ponto p1, Ponto p2)
        {
            for (int i = 0; i < this.pontosLigados.Count; i++)
            {
                if (this.pontosLigados[i][0].Equals(p1) && this.pontosLigados[i][1].Equals(p2)
                    || this.pontosLigados[i][0].Equals(p2) && this.pontosLigados[i][1].Equals(p1))
                    return true;
            }
            
            return false;
        }

        #endregion

        #region Descobrir CSP

        /// <summary>
        /// A partir das ligações entre os pontos, este método procura pelos triângulos formados pelas ligações.
        /// Este método é importante, pois cada triângulo será uma das variáveis do CSP.
        /// </summary>
        private void acharTriangulos()
        {
            this.triangulos = new List<Triangulo>();

            Ponto p1;
            Ponto p2;
            Ponto p3;
            //tenta achar ligacoes do tipo p1->p2->p3
            for (int i = 0; i < this.pontosLigados.Count; i++)
            {
                //p1->p2
                p1 = this.pontosLigados[i][0];
                p2 = this.pontosLigados[i][1];

                //p2->p3
                for (int j = i + 1; j < this.pontosLigados.Count; j++)
                {
                    if(this.pontosLigados[j][0].Equals(p2)){
                        p3 = this.pontosLigados[j][1];
                        achaP3P1(p1, p2, p3, i); //p3->p1
                        }

                    else if (this.pontosLigados[j][1].Equals(p2))
                    {
                        p3 = this.pontosLigados[j][0];
                        achaP3P1(p1, p2, p3, i); //p3->p1
                    }
                }
            }
        }

        /// <summary>
        /// Método chamado durante algoritmo que procura pelos triângulos gerados no mapa. Dados os pontos
        /// p1, p2 e p3, o algoritmo já achou ligações do tipo p1->p2 e p2->p3. Agora falta achar a última
        /// ligação: p3->p1.
        /// </summary>
        /// <param name="p1">Ponto 1</param>
        /// <param name="p2">Ponto 2</param>
        /// <param name="p3">Ponto 3</param>
        /// <param name="i">índice (começa em zero) da lista de ligações em que a ligação p1->p2 está</param>
        private void achaP3P1(Ponto p1, Ponto p2, Ponto p3, int i)
        {
            for (int j = i + 1; j < this.pontosLigados.Count; j++)
            {
                if (this.pontosLigados[j][0].Equals(p3) && this.pontosLigados[j][1].Equals(p1))
                {
                    Triangulo triangulo = new Triangulo(p1, p2, p3, this.triangulos.Count + 1);
                    this.triangulos.Add(triangulo);
                    break;
                }

                else if (this.pontosLigados[j][1].Equals(p3) && this.pontosLigados[j][0].Equals(p1))
                {
                    Triangulo triangulo = new Triangulo(p1, p2, p3, this.triangulos.Count + 1);
                    this.triangulos.Add(triangulo);
                    break;
                }
            }
        }

        /// <summary>
        /// Procura dentre os triângulos do mapa quais são os adjacentes
        /// </summary>
        private void acharTriangAdjacentes()
        {
            this.triangAdjacentes = new List<Triangulo[]>();

            //Compara triângulos 2 a 2
            for (int i = 0; i < this.triangulos.Count; i++)
            {
                for (int j = i + 1; j < this.triangulos.Count; j++)
                {
                    if (Geometria.SaoTriangAdjacentes(this.triangulos[i], this.triangulos[j]))
                        this.triangAdjacentes.Add(new Triangulo[2] { this.triangulos[i], this.triangulos[j] });
                }
            }
        }

        /// <summary>
        /// A partir do mapa atual, configura as variáveis e as restrições do CSP
        /// </summary>
        private void montaVariaveisRestricoes()
        {
            this.variaveis = new List<int>();
            for (int i = 0; i < this.triangulos.Count; i++)
            {
                this.variaveis.Add(this.triangulos[i].Id);
            }

            this.restricoes = new List<int[]>();
            for (int i = 0; i < this.triangAdjacentes.Count; i++)
            {
                this.restricoes.Add(new int[2] { this.triangAdjacentes[i][0].Id, this.triangAdjacentes[i][1].Id });
            }
        }

        #endregion

        #region Métodos Debug

        /// <summary>
        /// Imprime o mapa em um arquivo csv, com a coordenada dos pontos e suas ligações (utilizado para Debug)
        /// </summary>
        public void imprimeDados(string caminhoArquivo)
        {
            StringBuilder stringBuilder = new StringBuilder();

            //Pontos
            for (int i = 0; i < this.pontos.Count; i++)
            {
                stringBuilder.Append(this.pontos[i].Id + ";" + this.pontos[i].X + ";" + this.pontos[i].Y + "\n");
            }

            stringBuilder.Append("\n\n\n");

            //Ligações entre Pontos
            for (int i = 0; i < this.pontosLigados.Count; i++)
            {
                stringBuilder.Append(this.pontosLigados[i][0].Id + ";" + this.pontosLigados[i][1].Id + "\n");
            }

            stringBuilder.Append("\n\n\n");

            //Triângulos
            for (int i = 0; i < this.triangulos.Count; i++)
            {
                stringBuilder.Append(this.triangulos[i].Id + ";" + this.triangulos[i].Vertices[0].Id + ";" + this.triangulos[i].Vertices[1].Id + ";" + this.triangulos[i].Vertices[2].Id + "\n");
            }

            stringBuilder.Append("\n\n\n");

            //Adjacências entre triângulos
            for (int i = 0; i < this.triangAdjacentes.Count; i++)
            {
                stringBuilder.Append(this.triangAdjacentes[i][0].Id + ";" + this.triangAdjacentes[i][1].Id + "\n");
            }

            File.WriteAllText(caminhoArquivo, stringBuilder.ToString());
        }

        #endregion
    }
}
